package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:188. 买卖股票的最佳时机 IV
 * <p>
 * User:Mr.Du
 * Date:2024/7/30
 * Time:14:59
 */
public class MaxProfitIV {


    /**
     * 计算给定价格数组中，最多进行k次交易的情况下，能够获得的最大利润。
     * 该方法使用动态规划的思想，通过构建一个三维数组dp来存储中间结果。
     * dp[i][j][0]表示第i天进行j次交易后持有股票的最大利润，
     * dp[i][j][1]表示第i天进行j次交易后不持有股票的最大利润。
     *
     * @param k 最多可以进行的交易次数
     * @param prices 价格数组，表示每天的股票价格
     * @return 返回能够获得的最大利润
     */
    public int maxProfit(int k, int[] prices) {
        // n表示价格数组的长度
        int n = prices.length;
        // 初始化动态规划数组，dp[i][j][0]和dp[i][j][1]分别表示第i天进行j次交易后持有和不持有股票的最大利润
        int[][][] dp = new int[n + 1][k + 1][2];

        // 初始化第一天进行交易的情况，假设第一天买入股票，则初始利润为-prices[0]
        for (int i = 0; i <= k; i++) {
            dp[0][i][1] = -prices[0];
        }

        // 遍历每一天和每一次交易，更新动态规划数组
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                // 更新第i天进行j次交易后持有股票的最大利润，比较保持上一天持有状态和前一天卖出后状态两种情况
                dp[i + 1][j][0] = Math.max(dp[i][j][0], dp[i][j][1] + prices[i]);
                // 更新第i天进行j次交易后不持有股票的最大利润，比较保持上一天不持有状态和前一天买入后状态两种情况
                // 注意，由于不能同时进行两次交易，所以在进行第j次交易时，最多只能使用前j-1次交易的机会买入
                dp[i + 1][j][1] = Math.max(dp[i][j][1], dp[i][j - 1][0] - prices[i]);
            }
        }

        // 返回最后一天进行k次交易后不持有股票的最大利润
        return dp[n][k][0];
    }

    /**
     * 计算给定价格数组中，最多进行k次交易的情况下，能够获得的最大利润。
     * 该方法使用动态规划的思想，通过一个二维数组dp来存储每个状态下的最大利润。
     * dp[i][0]表示进行i次交易且当前未持有股票时的最大利润，
     * dp[i][1]表示进行i次交易且当前持有股票时的最大利润。
     *
     * @param k 允许进行的最大交易次数
     * @param prices 价格数组
     * @return 最大利润
     */
    public int maxProfit1(int k, int[] prices) {
        int n = prices.length; // 总天数
        int[][] dp = new int[k + 1][2]; // 动态规划数组，k + 1表示k次交易，2表示两种状态：持有股票和不持有股票

        // 初始化：表示尚未进行任何交易时，持有股票的状态为负无穷大（因为持有股票会产生亏损）
        for (int i = 0; i <= k; i++) {
            dp[i][1] = -prices[0];
        }

        // 遍历每一天，更新动态规划数组
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                // 更新不持有股票时的最大利润：比较保持昨天不持有状态和昨天持有状态卖股票后的利润
                dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
                // 更新持有股票时的最大利润：比较保持昨天持有状态和昨天不持有状态买股票后的利润
                dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - prices[i]);
            }
        }

        // 返回进行k次交易且不持有股票时的最大利润
        return dp[k][0];
    }

}
